package algorithms.leaning.class11;

/**
 * 二叉树结构如下定义：
 * Class Node {
 * V value;
 * Node left;
 * Node right;
 * Node parent;
 * }
 * 给你二叉树中的某个节点，返回该节点的后继节点
 * 后继节点定义：中序遍历列表中下一个节点就是后继节点
 *
 * @author guichang
 * @date 2021/6/10
 */

@SuppressWarnings("all")
public class Code6_二叉树_后继节点 {
    // 1. 有右树，则结果就是右树的最左孩子
    // 2. 无右树，如果我是我父亲的右孩子则继续往上，否则返回父节点

    class Node {
        int value;
        Node left;
        Node right;
        Node parent;
    }

    /**
     * 找后继节点
     *
     * @param node 当前节点
     */
    public Node nextNode(Node node) {
        if (node == null) {
            return null;
        }
        // 有右树，则结果就是右树的最左孩子
        if (node.right != null) {
            Node n = node.right;
            while (n.left != null) {
                n = n.left;
            }
            return n;
        }
        // 无右树，则找第一个父节点的右节点不是自己的父节点
        else {
            Node n = node;
            Node parent = node.parent;
            // 父节点不为空且父节点的右孩子不是自己
            while (parent != null && parent.right != n) {
                // 继续找
                n = parent;
                parent = n.parent;
            }
            return parent;
        }
    }

}